1. Field of the Invention
The present invention relates in general to computer-based methods for designing and analyzing integrated circuit (IC) layouts and in particular to a method for estimating time delays through signal paths of an IC layout.
2. Description of Related Art
An IC designer typically produces an IC design in the form of a netlist referencing cells (circuit components) to be included in the IC and indicating how the cell terminals are to be interconnected to one another and to the IC's input/output (I/O) terminals through conductors (nets) within the IC. A cell library describes each kind of cell that may be included in the IC design, and the netlist indicates the nature of each cell to be included in the IC by referencing the entry in the cell library for that particular type of cell.
While the netlist references cells to be included in the IC and indicates which of their terminals are to be interconnected, it does not indicate where or how each cell is to be placed or oriented in an IC layout and does not indicate how the nets are to be routed between the cell and I/O terminals they are to interconnect. Therefore, after producing the netlist, an IC designer usually employs a computer-aided placement and routing (P&R) tool to detail the IC's layout by indicating how each cell referenced by the netlist is to be positioned and oriented and how nets are to be routed on the various layers of the IC between the cell and IC I/O terminals.
Although a typical IC can include large numbers of cells and nets, for illustrative purposes FIG. 1 shows a simplified plan view of a layout for an IC including only eight cells 1–8 and a set of fourteen nets A–N linking terminals of those cells to one another and to a set of five IC input terminals I1–I5 and two output terminals O1 and O2.
The layout produced by a P&R tool must satisfy many constraints on the IC design, including timing constraints on signal path delays. A “signal path” is formed by cells and/or conductors that logically interconnect two circuit nodes A and B such that a state change in a signal applied to node A can produce a subsequent state change at node B. Such a signal path has a timing constraint when a time delay between the change in signal states at nodes A and B must be within some maximum limit. For example, as illustrated in FIG. 2, in a synchronous logic circuit, a block of logic 10 within an IC receives all of its input signals from other parts of the IC via a register 12, and transmits all of its output signals to other parts of the IC via another register 14. The two registers 12 and 14 may be clocked by the same or different clock signals CLK1 and CLK2. One constraint on the IC design could be that logic block 10 must fully respond to a state change in any output signal of register 12 occurring on an edge of the CLK1 signal by adjusting states of the signals it supplies to register 14 before a next edge of the CLK2 signal clocking register 14. The gates and nets within logic block 10 may form many signal paths between nodes at the output of register 12 and nodes at the inputs of register 14, and each such signal path is constrained to a path delay that is less than a time difference between edges of clock signals CLK1 and CLK2.
For example if cells 1 and 2 of FIG. 1 are registers clocked by some clock signal CLK1 and cell 8 is a register clocked by another clock signal CLK2, then each of the various signal paths extending from any output of registers 1 and 2 to any input of register 8 should have a path delay no greater than a time difference between edges of the CLK1 and CLK2 signals.
After a conventional P&R tool generates an integrated circuit layout, it is often necessary for the designer to employ a computer-aided timing verification tool to compute time delays through the various signal paths within the IC to determine whether the layout meets various timing constraints on those signal paths. When path delays within one or more signal paths fail to meet timing constraints, the P&R tool will have to revise the layout to reduce delays in those signal paths.
The delay of any signal path is the sum of the delays through all gates forming that signal path and the delays through portions of the nets interconnecting those gates. The cell library typically includes information about the signal path delay through each cell, but the delays through arcs of the nets linking the cells must be estimated based on the layout of the nets. The path delay through a conductor forming a part (or “arc”) of a net is usually function primarily of the resistance and capacitance components of the impedance of that particular arc. (Although the inductance of an arc also influences the path delay through an arc of a net, it does so to a lesser extent and is usually ignored when calculating path delays within an IC.) In order for a signal edge to propagate through an arc, the signal must charge or discharge the arc's capacitance, and the time required to do that is proportional to the product of its resistance and capacitance. The time required for a signal edge to propagate through an arc of a net is therefore largely a function of its length and of its resistance and capacitance per unit length. Thus for a timing analysis tool to determine how long signal edge require to propagate through any portion of a net, it is necessary for the tool to know the resistance and capacitance of the arcs forming that net.
Accordingly after a P&R tool has generated an IC layout, the designer may employ a conventional resistance/capacitance (RC) extraction tool to process the IC layout to determine the resistance and capacitance of the various arcs of each net. Each arc is conductor having an amount of resistance per unit length that is mainly a function of the cross-sectional area of the conductor and the amount of its capacitance per unit length of the conductor is a mainly a function of the width of the conductor, the distance from the conductor to nearby power and ground planes, and the dielectric constant of the insulating material between the conductor and power and ground planes. An RC extraction tool therefore may estimate the impedance of each arc based on the structure of the conductor forming the arc and on characteristics of the surrounding portions of the IC that influence its capacitance.
A net may have many arcs for which an RC extraction tool must separately calculate impedance values because various sections or branches of a net may have differing impedance environments, and because some arcs of a net may be included in some signal paths while others are not. For example FIG. 3 illustrates net G of FIG. 1 as being formed by six arcs G1–G6 for which resistance and capacitance values are separately estimated. Various vias 16 and 18 linking arcs residing on different layers may themselves be treated as separate arc. The RC extraction tool stores the resistance and capacitance data it generates for each arc of a net in a database accessible to a timing analysis tool. Since a large IC can have thousands or millions of nets, each of which may include several arcs, an RC extraction database can be very large.
FIG. 4 illustrates a typical prior process of generating an IC layout and then analyzing the layout to determine delays through paths within the layout. A P&R tool 22 processes a netlist 23 and a cell library 24 to produce a layout database 26 indicating where each cell of the IC is to be positioned within an IC layout and how all nets are routed. An RC extraction tool 28, read accessing layout database 26, generates an RC extraction database 30 indicating the resistance and capacitance of each arc of each net. A timing analysis tool 32 then processes netlist 23, cell library 24 and RC extraction database 30 to generate a path delay database 34 indicating the delay though each signal path of interest referenced by path data 36 supplied as input to the timing analysis tool. The RC extraction database 30 is usually stored on a hard disk accessible to the computer programmed to act as timing analysis tool 32. But timing analysis tool 32 may generate a copy 38 of the entire RC extraction database in random access memory (RAM) before it begins calculating path delays so that whenever it requires RC extraction data for a net as it calculates path delays, it can read access the data in the RAM-based database 30 through a relatively fast RAM access, rather than from the disk-based database 30 through a relatively slow disc access.
FIG. 5 illustrates how prior art analysis tool 32 of FIG. 4 accesses RC extraction data when determining signal path delays. After selecting a signal path of interest (step 40), the tool consults netlist 32 to determine which cells are included in the selected signal path, and then consults cell library 24 to determine the path delay through each cell (step 44) and to determine the input or output impedance at each cell terminal. The tool also determines which arcs are included in the selected signal path (step 46) and reads the RC data for nets containing each arc from the RC extraction database (step 48). The tool then calculates the total signal path delay based on the data obtained from the cell library and from the RC extraction database (step 50). When there is another signal path of interest (step 52), the tool selects that signal path at step 40 and then repeats steps 42–50 to acquire the RC extraction and cell data for the nets and cells forming that signal path, and to calculate the delay for that signal path. The tool continues to loop through steps 40–52 in this manner until it has computed the path delay for each signal path of interest.
Note that as the timing analysis tool 32 calculates the path delay for each signal path of interest, it may have to access the RC extraction database many times to obtain the RC extraction data for each net that may be included in the signal path. Since arcs of particular net may be included in many different signal paths, timing analysis tool 32 may have to access RC extraction database 38 for the same net many times as it calculates path delays for all of the paths incorporating parts of that net. Since a computer takes substantially more time to read access data stored on a hard disk than to read access data stored in a random access memory, that is why prior art timing analysis tool 32 may initially copy the entire disk-based RC extraction database into random access memory (RAM) to form a RAM-based RC extraction database 38 (FIG. 4). Thereafter, whenever timing analysis tool 32 needs to obtain RC extraction data for a particular net when calculating the delay through some signal path of interest, it can read the data from RAM-based RC extraction database 38 rather than from the disk-based RC extraction database 30. The timing analysis tool need only read the data for each net once out of the hard disk when generating the RAM-based version 38 of the database, even though it may thereafter need to read access the data for any particular net several times in the course of calculating path delays.
However an RC extraction database 38 for a large IC layout, such as for a deep sub-micron IC design having millions of arcs, can be so large that a computer programmed to implement a timing analysis tool may not have the memory resources the tool needs to store an copy of the entire database. When only a portion of the RC extraction database can be stored in RAM at any one time, it is may be necessary for timing analysis tool 32 to read access the disk version 30 of the database many times to obtain RC extraction data for a net included in more than one signal path of interest for which path delay is to be calculated. Therefore what is needed is a method by which a timing verification tool can calculate path delays without having to read access disk-based RC extraction data for any net more than once, and without having to create a copy of the entire database in random access memory.